package com.future;

import java.util.PriorityQueue;

/**
 * Description:
 * 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
 * <p>
 * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
 * <p>
 * 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
 * <p>
 * 说明：
 * <p>
 * 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
 * 翻转后单词间应当仅用一个空格分隔。
 * 翻转后的字符串中不应包含额外的空格。
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "the sky is blue"
 * 输出："blue is sky the"
 * 示例 2：
 * <p>
 * 输入：s = " hello world "
 * 输出："world hello"
 * 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
 * 示例 3：
 * <p>
 * 输入：s = "a good example"
 * 输出："example good a"
 * 解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
 * 示例 4：
 * <p>
 * 输入：s = "  Bob    Loves  Alice   "
 * 输出："Alice Loves Bob"
 * 示例 5：
 * <p>
 * 输入：s = "Alice does not even like bob"
 * 输出："bob like even not does Alice"
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 104
 * s 包含英文大小写字母、数字和空格 ' '
 * s 中 至少存在一个 单词
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2021/10/5 14:59
 */
public class Solution_reverseWords_151 {

    public static void main(String[] args) {

        StringBuilder sb = new StringBuilder();

        sb.insert(0, "ab");
        sb.insert(0, "cd");
        sb.insert(0, "ef");

        System.out.println(sb.toString());

        System.out.println("=====");
        String s = "ab cd ef";
        s = "the sky is blue";
        s = " hello world ";
        s = "a good  example";
        System.out.println("原始：" + s);
        System.out.println("结果：" + reverseWords(s));

    }

    /**
     * 1、一次遍历，遇到空格为一个单词，记录该单词在字符串中的起始位置
     * 2、剪切该单词，前插入到StringBuilder中
     * 3、一个单词除了末尾，其他单词用空格分割，连续空格需要进行处理
     *
     * @param s
     * @return
     */
    public static String reverseWords(String s) {
        if (null == s || s.length() == 0) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        // 去掉首位空格
        s = s.trim();
        for (int i = 0; i < s.length(); i++) {
            int start = i;
            // 走到一个单词末尾
            while (i < s.length() && s.charAt(i) != ' ') {
                i++;
            }
            // 插入第一位
            String st = s.substring(start, i);
            sb.insert(0, st);
            // 有多个连续空格场景，只需要拼接一个空格就够
            while (i < s.length() && s.charAt(i) == ' ') {
                // 当前为空格，继续遍历，直到最后一个空格
                i++;
            }
            // 注意，此时已经来到下个单词的第一个下标了，需要回退到上一个下标
            i--;
            if (i < s.length() - 1) {
                sb.insert(0, " ");
            }
        }
        return sb.toString();
    }
}
